數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法得到:
(1)順序存儲方法
該方法把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里,結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。
由此得到的存儲表示稱為順序存儲結(jié)構(gòu)(Sequential Storage Structure ),通常借助程序語言的數(shù)組描述。
該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實現(xiàn)順序存儲。
(2)鏈接存儲方法
該方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰,結(jié)點間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)(Linked Storage Structure), 通常借助于程序語言的指針類型描述。
(3)索引存儲方法
該方法通常在儲存結(jié)點信息的同時,還建立附加的索引表。索引表由若干索引項組成。若每個結(jié)點在索引表中都有一個索引項,則該索引表稱之為稠密索引(Dense Index )。若一組結(jié)點在索引表中只對應(yīng)一個索引項,則該索引表稱為稀疏索引(Spare Index)。索引項的一般形式是:關(guān)鍵字、地址。
關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密索引中索引項的地址指示結(jié)點所在的存儲位置;稀疏索引中索引項的地址指示一組結(jié)點的起始存儲位置。
(4)散列存儲方法
該方法的基本思想是:根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。
四種基本存儲方法,既可單獨使用,也可組合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲映像。
同一邏輯結(jié)構(gòu)采用不同的存儲方法,可以得到不同的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu),視具體要求而定,主要考慮運算方便及算法的時空要求。
數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系
數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算這三方面是一個整體。孤立地去理解一個方面,而不注意它們之間的聯(lián)系是不可取的。 存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可或缺的一個方面:同一邏輯結(jié)構(gòu)的不同存儲結(jié)構(gòu)可冠以不同的數(shù)據(jù)結(jié)構(gòu)名稱來標(biāo)識。